package cn.edu.xjtu.tencent.formal;

import java.util.ArrayList;

/**
 * @author Hydrion-QLz
 * @date 2022-09-13 20:59
 * @description
 */
public class fifth {
    int length = 0;

    public ListNode solve(ListNode S) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        int max = 0;
        int max_idx = 0;
        int count = 0;
        while (S != null) {
            list.add(S.val);
            if (S.val >= max) {
                max = S.val;
                max_idx = count;
            }
            S = S.next;
            count++;
        }
        // 输出结果
        int length = count + 1;
        ListNode head = new ListNode(max);
        ListNode temp = head;
        int startIdx = max_idx;
        int nextIdx = (startIdx + 1) % length;
        while (nextIdx != startIdx) {
            temp.next = new ListNode(list.get(nextIdx));
            temp = temp.next;
            nextIdx = (nextIdx + 1) % length;
        }
        return head;
    }

    public ListNode solve1(ListNode S) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        int min = Integer.MAX_VALUE;
        ArrayList<Node> min_idx = new ArrayList<>();
        int count = 0;

        // 第一轮统计最小值
        while (S != null) {
            list.add(S.val);
            if (S.val < min) {
                min = S.val;
                min_idx.clear();
            }
            if (S.val <= min) {
                min_idx.add(new Node(count, count));
            }
            S = S.next;
            count++;
        }
        length = count + 1;


        // 向右侧推进，直到找到最小值
        while (min_idx.size() != 1) {
            ArrayList<Node> tempList = new ArrayList<>();
            min = Integer.MAX_VALUE;
            for (int i = 0; i < min_idx.size(); i++) {
                Node node = min_idx.get(i);
                if (list.get(node.nextIdx()) < min) {
                    min = list.get(node.nextIdx());
                    tempList.clear();
                }
                if (list.get(node.nextIdx()) <= min) {
                    tempList.add(new Node(node.zero, node.nextIdx()));
                }
            }
            min_idx = tempList;
        }

        // 输出结果
        ListNode head = new ListNode(min);
        ListNode temp = head;
        int startIdx = min_idx.get(0).zero;
        int nextIdx = (startIdx + 1) % length;
        while (nextIdx != startIdx) {
            temp.next = new ListNode(list.get(nextIdx));
            temp = temp.next;
            nextIdx = (nextIdx + 1) % length;
        }
        return head;
    }

    class Node {
        int zero;
        int nowIdx;

        public Node(int zero, int nowIdx) {
            this.zero = zero;
            this.nowIdx = nowIdx;
        }

        public int nextIdx() {
            return (nowIdx + 1) % length;
        }
    }
}
